class Solution {
    public:
        int findTargetSumWays(vector<int>& nums, int target) {
            int n = nums.size(),sum = 0;
            for(auto& x: nums) sum+=x;
            int m = (sum+target)/2;
            if(m < 0|| (sum+target)%2 == 1) return 0;
            vector<vector<int>> dp(n+1,vector<int>(m+1));
            //dp[i][j]表示1-i的数组凑齐j的数目
            dp[0][0] = 1;
            for(int i = 1 ; i < n+1;i++){
                for(int j = 0 ; j < m+1; j++){
                    dp[i][j] = j>=nums[i-1] ?  dp[i-1][j-nums[i-1]]+dp[i-1][j]:dp[i-1][j];
                }
            }
            return dp[n][m];
    
        }
    };